package offer;

public class TreeToDoublyList_36 {
    Node pre;
    Node ans;
    public Node treeToDoublyList(Node root) {
        if(root == null)return null;
        build(root);
        ans.left = pre;
        pre.right = ans;
        return ans;


    }

    public void build(Node root){
        if(root == null) return;

        build(root.left);

        if(pre != null){
            pre.right = root;
        }else{
            // 第一次
            ans = root;
        }
        root.left = pre;
        pre = root;

        build(root.right);

    }

    Node pre2;
    Node cur2;
    public Node treeToDoublyList2(Node root) {

        if(root == null) return null;
        build2(root);
        pre2.right = cur2;
        cur2.left = pre2;
        return cur2;
    }

    public void build2(Node root){
        if(root == null) return;

        build2(root.left);

        if(pre2 != null){
            pre2.right = root;
        }else{
            cur2 = root;
        }

        root.left = pre2;
        pre2 = root;

        build2(root.right);
    }


    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
}
